package com.dragon.modules.yuegou.web;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * 树.
 * 
 * @author liuwu
 * @date 2018年3月6日
 *
 * @param <E>
 *            节点元素类型
 */
public interface Tree<E> extends Collection<E> {

	/**
	 * 树的深度. 树的根节点深度代表着树的深度.
	 * 
	 * <p>
	 * 从树中获取的节点, 判断其层级时, 使用{@code node.depth()}是不够的, 这是节点在节点树中的绝对深度, 考虑子树的存在,
	 * 要获取节点在当前树中的深度必须使用相对深度{@code node.depth() - tree.depth()}.
	 * 
	 * @return depth
	 */
	int depth();

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * 树的大小, 节点总数
	 * 
	 * @return 除虚根之外的节点总数
	 */
	int size();

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * 返回数组的顺序由{@link #iterator()}顺序决定
	 */
	Object[] toArray();

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * 返回数组的顺序由{@link #iterator()}顺序决定
	 */
	<T> T[] toArray(T[] a);

	/**
	 * 添加一个根节点元素, 添加的元素会作为树的跟节点存在.
	 * 
	 * @param root
	 *            根节点元素
	 * @return 如果不支持多根, 并且当前树中已经存在一个根节点则会添加失败. 添加成功返回{@code true},
	 *         添加失败返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code root} is {@code null}.
	 */
	boolean add(E root);

	/**
	 * 添加一个元素, 把元素添加到指定的父节点下, 作为父节点的子节点.
	 * 
	 * @param element
	 *            节点元素
	 * @param parent
	 *            指定的父节点元素
	 * @return 如果添加成功返回{@code true}, 如果相应父节点找不到则添加失败, 返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code child} or {@code parent} is {@code null}.
	 */
	boolean add(E element, E parent);

	/**
	 * 移除指定元素. 当被移除的元素所在节点存在子节点时, 其子节点也会一并移除.
	 */
	boolean remove(Object e);

	/**
	 * 批量添加根节点元素, 添加的元素会作为树的跟节点存在.
	 * 
	 * @param roots
	 *            根节点元素集合
	 * @return 如果不支持多根, 并且当前树中已经存在一个根节点则会添加失败; 如果不支持多根, 并且当前树为空树, 且添加的元素多余1时,
	 *         只有第一个元素会添加成功. 调用方法后集合发生了改变返回{@code true}, 否则返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code root} is {@code null}.
	 */
	boolean addAll(Collection<? extends E> roots);

	/**
	 * 批量添加元素, 把元素添加到指定的父节点下, 作为父节点的子节点.
	 * 
	 * @param parent
	 *            指定的父节点元素
	 * @return 如果添加成功返回{@code true}, 如果相应父节点找不到则添加失败, 返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code childs} or {@code parent} is {@code null}.
	 */
	boolean addAll(Collection<? extends E> childs, E parent);

	/**
	 * 移除所有在指定集合中存在的元素. 调用后, 当前树中不存在任何指定集合中的元素. 当被移除的元素所在节点存在子节点时, 其子节点也会一并移除.
	 * 
	 * @param elements
	 *            要从当前树中移除的元素集合
	 * @return 如果调用此方法后当前树发生了改变则返回{@code true}, 否则返回{@code false}.
	 */
	boolean removeAll(Collection<?> elements);

	/**
	 * 清除这颗树的所有元素, 清除后这颗树会变成空树.
	 */
	void clear();

	/**
	 * 获取当前树的跟节点.
	 * 
	 * @return 如果当前树不存在跟节点(空树)则返回{@code null}, 如果当前树存在多个根节点, 则返回第一个根节点.
	 */
	Node<E> root();

	void root(E e);

	/**
	 * 树遍历器
	 * 
	 * @param strategy
	 *            遍历策略
	 * @return an Iterator over the elements in this collection
	 * @see IteratorStrategy#BREADTH_FIRST
	 * @see IteratorStrategy#DEPTH_FIRST
	 * @see IteratorStrategy#DESCENDING_BREADTH_FIRST
	 * @see IteratorStrategy#DESCENDING_DEPTH_FIRST
	 */
	TreeIterator<E> treeIterator(IteratorStrategy strategy);

	/**
	 * 替换节点元素
	 * 
	 * @param old
	 *            就节点元素
	 * @param element
	 *            节点元素
	 * @return 如果替换成功返回{@code true}; 如果就节点未找到, 则替换失败, 返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code old} or {@code element} is {@code null}.
	 */
	boolean replace(E old, E element);

	/**
	 * 移动子树. 把{@code element}节点移动到{@code parent}节点下, 作为{@code parent}的子节点.
	 * 
	 * @param element
	 *            要移动的节点元素
	 * @param parent
	 *            目标父节点元素
	 * @return 如果移动成功返回{@code true}; 如果要移动的节点或目标节点不存在, 则移动失败, 返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code element} or {@code parent} is {@code null}.
	 */
	boolean move(E element, E parent);

	/**
	 * 获取元素所在节点
	 * 
	 * @param element
	 *            元素
	 * @return 节点, 如果未找到则返回null
	 */
	Node<E> get(Object element);

	/**
	 * 获取元素所在的子树. 获取的子树依然被当前树引用着, 当在返回的子树实例中进行更改时, 当前树也会跟着变化.
	 * 
	 * @param element
	 *            元素
	 * @return 以指定元素为根的子树. 如果元素不存在则返回空树, 对返回的空树进行修改不会影响到当前树.
	 * @throws NullPointerException
	 *             if {@code element} is {@code null}.
	 */
	Tree<E> subTree(Object element);

	/**
	 * 向当前树中添加一棵树, 添加后输入的树的根会作为{@code parent}元素所在节点的子节点..
	 * 
	 * <p>
	 * 这个操作不会对输入的树进行任何更改, 添加完毕后两颗树的更改亦不会相互影响.
	 * 
	 * @param tree
	 *            要添加到当前树中的树.
	 * @param parent
	 * @return 如果添加后当前树发生了改变则返回{@code true}, 否则返回{@code false}.
	 * @throws NullPointerException
	 *             if {@code tree} or {@code parent} is {@code null}.
	 */
	boolean addTree(Tree<E> tree, E parent);

	/**
	 * 剪枝. 从当前树中剪除以指定元素为根的子树.
	 * 
	 * <p>
	 * {@code cut}方法对当前树的影响与{@code remove}方法是一样的, 不同的是{@code cut}方法会把移除的子树返回.
	 * 
	 * @param element
	 *            需要被移除的子树的根节点元素.
	 * @return 被移除的节点树, 当没有移除任何节点时返回空树.
	 * @throws NullPointerException
	 *             if {@code element} is {@code null}.
	 */
	Tree<E> cut(Object element);

	/**
	 * 判断当前树是否包含另外一颗树. 等价的说法是判断另一颗树是否是当前树的子树.
	 * {@code tree.containsTree(tree.subTree(e))}恒成立.
	 * <p>
	 * 空树是任何数的子树.
	 * 
	 * @param tree
	 *            树
	 * @return 如果树是此树的子树(树被当前树包含)则返回true, 否则返回false.
	 */
	boolean containsTree(Tree<E> tree);

	/**
	 * 判断树中是否包含某个路径. 路径指的是从根节点到某个元素的路径.
	 * 
	 * @param path
	 *            路径.
	 * @return 如果此树包含指定的路径则返回true. 特别的, 如果{@code path}是空列表, 则返回false.
	 */
	boolean containsPath(List<E> path);

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * 树的hashCode与树中所有元素的hashCode以及元素的组织结构有关.
	 */
	int hashCode();

	/**
	 * 判断两颗树是否相等, 如果两颗树所有的元素相等, 并且元素的组织结构一致则表明两颗树相等. 与树的实现类无关, 即如果满足了上文的两个条件,
	 * 即使两颗树的实现类不同, 此方法也应该返回true.
	 * 
	 * <p>
	 * 很显然, 空树与空树是相等的.
	 * 
	 * <p>
	 * {@inheritDoc}
	 */
	boolean equals(Object o);

	/**
	 * 树遍历策略
	 * 
	 * @author liuwu
	 * @date 2018年3月6日
	 *
	 */
	enum IteratorStrategy {

		/**
		 * 宽度(广度)优先策略.
		 * 
		 * 例:
		 * 
		 * <pre>
		 * A
		 * |--B
		 * |--|--D
		 * |--|--E
		 * |--C
		 * |--|--F
		 * </pre>
		 * 
		 * 使用宽度优先策略遍历得到的序列是: ABCDEF
		 */
		BREADTH_FIRST,

		/**
		 * 深度优先策略.
		 * 
		 * 例:
		 * 
		 * <pre>
		 * A
		 * |--B
		 * |--|--D
		 * |--|--E
		 * |--C
		 * |--|--F
		 * </pre>
		 * 
		 * 使用宽度优先策略遍历得到的序列是: ABDECF
		 */
		DEPTH_FIRST,

		/**
		 * 逆序的宽度(广度)优先策略. {@code DESCENDING}指的是在遍历兄弟节点时按照逆序遍历, 并非把宽度优先策略的遍历结果逆序, 不管何种策略,
		 * 第一个遍历的总是根节点.
		 * 
		 * 例:
		 * 
		 * <pre>
		 * A
		 * |--B
		 * |--|--D
		 * |--|--E
		 * |--C
		 * |--|--F
		 * </pre>
		 * 
		 * 使用宽度优先策略遍历得到的序列是: ACBFED
		 */
		DESCENDING_BREADTH_FIRST,

		/**
		 * 逆序的深度优先策略. {@code DESCENDING}指的是在遍历兄弟节点时按照逆序遍历, 并非把深度优先策略的遍历结果逆序, 不管何种策略,
		 * 第一个遍历的总是根节点.
		 * 
		 * 例:
		 * 
		 * <pre>
		 * A
		 * |--B
		 * |--|--D
		 * |--|--E
		 * |--C
		 * |--|--F
		 * </pre>
		 * 
		 * 使用宽度优先策略遍历得到的序列是: ACFBED
		 */
		DESCENDING_DEPTH_FIRST;
	}

	/**
	 * 树节点
	 * 
	 * @author liuwu
	 * @date 2018年3月6日
	 *
	 * @param <E>
	 */
	interface Node<E> extends Iterable<Node<E>> {

		/**
		 * 父节点
		 * 
		 * @return parent tree node, or null if no parent.
		 */
		Node<E> parent();

		/**
		 * 此节点存储的元素
		 * 
		 * @return element
		 */
		E element();

		/**
		 * 此节点的直接子节点列表, 此列表是不可变的, 任何改变此列表的操作都将抛出异常
		 * 
		 * @return child node list, never null, 如果没有孩子节点则返回空列表
		 */
		List<Node<E>> childs();

		/**
		 * 获取此节点的父节点列表, 按照从上至下的顺序排序.
		 * 
		 * @return parent nodes list
		 */
		default List<Node<E>> parents() {
			LinkedList<Node<E>> parents = new LinkedList<>();
			Node<E> parent = parent();
			while (parent != null) {
				parents.addFirst(parent);
				parent = parent.parent();
			}
			return parents;
		}

		/**
		 * 获取节点值为{@code element}的节点
		 * 
		 * <p>
		 * 如果存在多个值为{@code element}的节点, 则取第一个节点, 其顺序由{@link #iterator()}决定.
		 * 
		 * @param element
		 *            元素
		 * @return 获取到的节点, {@code null}表示不存在值为{@code element}的节点
		 */
		Node<E> get(Object element);

		/**
		 * 此节点的深度, 定义根节点的深度为0, 根节点的直接子节点的深度为1, 以此类推.
		 * 
		 * @return depth
		 */
		default int depth() {
			int depth = 0;
			Node<E> parent = parent();
			while (parent != null) {
				depth++;
				parent = parent.parent();
			}
			return depth;
		}

		/**
		 * 节点大小, 即以此节点为跟的节点树中所有节点的数量.
		 * 
		 * @return size
		 */
		default int size() {
			Iterator<Node<E>> itr = iterator();
			int size = 0;
			while (itr.hasNext()) {
				size++;
			}
			return size;
		}

		/**
		 * 判断是否为根节点, 如果此节点没有父节点即表明此节点为跟节点.
		 * 
		 * @return true如果此节点为根节点
		 */
		default boolean isRoot() {
			return parent() == null;
		}

		/**
		 * 判断是否为叶子节点, 如果此节点没有任何孩子节点则表明此节点为叶子节点
		 * 
		 * @return true如果此节点为叶子节点
		 */
		default boolean isLeaf() {
			return childs().isEmpty();
		}

		/**
		 * 判断此节点含有子节点
		 * 
		 * @return true如果此节点有子节点
		 */
		default boolean hasChild() {
			return !childs().isEmpty();
		}

		/**
		 * 对这个节点的直接子节点进行排序
		 * 
		 * @param comparator
		 *            排序比较器
		 */
		void sort(Comparator<E> comparator);

		/**
		 * 设置这个节点的元素
		 * 
		 * @param element
		 */
		void set(E element);

		/**
		 * 从树中移除此节点, 即让此节点与其父节点脱离关系.
		 */
		void remove();

		/**
		 * 清除此节点的孩子节点, 清除后此节点变为叶子节点. 如果此节点本身就是叶子节点则没有任何影响
		 */
		void clear();

		/**
		 * 向这个节点添加一个直接子节点
		 * 
		 * @param element
		 *            子节点元素
		 */
		void addChild(E element);

		/**
		 * 想这个节点添加一个直接子节点
		 * 
		 * @param element
		 *            子节点元素
		 * @param index
		 *            在直接子节点列表中的下标
		 * @throws IndexOutOfBoundsException
		 *             if the index is out of range
		 *             (<tt>index &lt; 0 || index &gt; childs().size()</tt>)
		 */
		void addChild(E element, int index);

		/**
		 * 移除直接子节点.
		 * 
		 * @param element
		 *            要移除的子节点元素值
		 * @return 如果成功移除则返回true, 否则(节点不存在)返回false.
		 */
		default boolean removeChild(E element) {
			Objects.requireNonNull(element);
			for (Node<E> node : childs()) {
				if (element.equals(node.element())) {
					node.remove();
					return true;
				}
			}
			return false;
		}

		/**
		 * 移除直接子节点.
		 * 
		 * @param index
		 *            直接子节点列表中的下标
		 * @return 如果成功移除则返回true, 否则返回false.
		 * @throws IndexOutOfBoundsException
		 *             if the index is out of range
		 *             (<tt>index &lt; 0 || index &gt; childs().size()</tt>)
		 */
		boolean removeChildAt(int index);

		/**
		 * 节点遍历器, 使用宽度优先遍历策略
		 */
		default Iterator<Node<E>> iterator() {
			return iterator(IteratorStrategy.BREADTH_FIRST);
		}

		/**
		 * 遍历器
		 * 
		 * @param strategy
		 *            遍历策略
		 * @return Node Iterator
		 */
		Iterator<Node<E>> iterator(IteratorStrategy strategy);

	}

}
